#ifndef _MUNIX_SKIPLIST_H
#define	_MUNIX_SKIPLIST_H
/******************************************************************************
 ** Name: skiplist.cpp                                                        **
 ** Description: SkipList datastructure implementation.                       **
 **                                                                           **
 ** Open Source Initiative (OSI) Approved License                             **
 **                                                                           **
 ** The contents of this file are subject to the terms of the                 **
 ** Common Development and Distribution License, Version 1.0 only             **
 ** (the "License").  You may not use this file except in compliance          **
 ** with the License.                                                         **
 **                                                                           **
 ** You can find a copy of the license in the license.txt within              **
 ** this distribution or at http://www.munixos.net/licensing.                 **
 ** Software distributed under the License is distributed on an "AS IS"       **
 ** basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.           **
 ** See the License for the specific language governing permissions           **
 ** and limitations under the License.                                        **
 **                                                                           **
 ** When distributing Covered Code, include this CDDL header in each          **
 ** file and include the License file at $HOME/license.txt.                   **
 ** If applicable, add the following below this header, with the indicated    **
 ** fields enclosed by brackets "[]" replaced with your own identifying       **
 ** information: Portions Copyright [yyyy] [name of copyright owner]          **
 **                                                                           **
 **                                                                           **
 ** Copyright (c) 2009-2010  Barry Gian James.                                **
 ** All rights reserved.                                                      **
 **                                                                           **
 ** Ref: $Id$
 ******************************************************************************/
// $Id$

// TODO implement research paper methods on skiplist for best performance
// Choose the i'th final to be i/2 + 1
#define DEFAULT_MAX_SKIPLISTS 11

template<class T, class K>
class SkipList {
public:
    SkipList(uint8 maxl, uint8 prob);
    SkipList() : SkipList(DEFAULT_MAX_SKIPLISTS, 50) { }
    SkipList(const SkipList& orig) = delete;
    virtual ~SkipList();

    void    Insert(K key, T val);
    T       Find(K key);
    void    Remove(K key);
    bool    CoinToss();
    uint8   NewRandLvl();
    
private:
    uint8   maxLists;
    uint8   currLists;
    long    prob;

    struct Node
    {
        K   key;
        T   value;
        Node * next, * up, * down;
    };
    Node ** head;
    Node * tail;
};

template<class T, class K>
SkipList<T,K>::SkipList<T,K>(uint8 maxl, uint8 prob)
{
    maxLists = maxl; this->prob = prob;
    currLists = 0;
    head = new Node[maxLists + 1];
    for(uint8 i = 0; i <= maxLists; i++)
        head[i] = new Node();
    tail = new Node();

    for(uint8 i = 0; i <= maxLists; i++)
    {
        head[i].next = tail;
        if (i > 0)
        {
            head[i].down = head[i-1];
            head[i-1].up = head[i];
        }
    }
    srandom(MTime::Now());
    prob = random() % 100;
}

template<class T, class K>
SkipList<T,K>::~SkipList<T,K>()
{
    for (uint8 i = 0; i <= maxLists; i++)
        delete head[i];
    delete [] head;
    delete tail;
}

template<class T, class K>
void SkipList<T,K>::Insert(K key, T val)
{

}

template<class T, class K>
uint8 SkipList<T,K>::NewRandLvl()
{
    uint8 newLvl = 0;
    while((newLvl < maxLists) && CoinToss())
        ++newLvl;
    return newLvl;
}

template<class T, class K>
T  SkipList<T,K>::Find(K key)
{
    // TODO Find
}

template<class T, class K>
void SkipList<T,K>::Remove(K key)
{

}

template<class T, class K>
bool SkipList<T,K>::CoinToss()
{
    uint8   chance = random() % 100;
    return (chance < prob);
}

#endif	/* _MUNIX_SKIPLIST_H */

